1. Field of the Invention
This invention relates to the general field of optical flow computation. More specifically, this invention relates to the field of integrated circuits that detect visual motion and measure optic flow.
2. Description of the Related Art
The term "optical flow" generally refers to the motion of texture seen by an agent (such as an animal or a robot) as a result of relative motion between the agent and other objects in the environment. It is well known that animals, especially insects, use information from the optical flow for depth perception and to move about in an environment without colliding into obstacles. Robotics and machine vision researchers have borrowed from these ideas in biology to build machine vision systems that successfully use optical flow for depth perception and obstacle avoidance. These successes verify that optical flow can indeed be used for depth perception and obstacles avoidance in real systems.
In robotics and machine vision, optical flow is mathematically expressed as a vector field either in the two-dimensional visual field 105 or on an image focal plane created by a lens. Both variations are used interchangeably in the subsequent description of the present invention.
The value of the optic flow vector 103 (FIG. 1) at a location in the visual field 105 (FIG. 1) refers to the velocity at which texture 107 (FIG. 1) is moving in that location of the visual field 105. To measure optical flow, typical machine vision systems grab sets of two-dimensional pixel array images using a camera, and use these sequential images to measure the optical flow field. In general, algorithms for computing optical flow from a set of images are computationally intensive, resulting in the need for a large amount of computing power for the computation of optical flow. This is because optical flow is a phenomena that has both spatial and temporal aspects, hence a large amount of data (two-dimensions of image and one dimension of time) needs to be processed. This is especially true if the image is sensed with a charge coupled device (CCD) or another pixel-structured type of image sensor. Almost all modem machine vision systems use such pixel-structured cameras. A discussion of the variety of algorithms used to measure optical flow is beyond the scope of this specification, however one successful and popular approach, the correlation method, is related to the operation of this sensor.
The correlation method of measuring optic flow will be qualitatively discussed by now referring to FIGS. 2a through 2c. FIGS. 2a and 2b show two successive frames or images of a video sequence. FIG. 2a shows the first frame 115, a location 117 in the first frame 115, and a block of texture 119 in the first frame. FIG. 2b shows the second frame 121, the search space 123 for a block that matches the first frame's block 119, and a best matching block 125. FIG. 2c shows a resulting optic flow vector 127. In the correlation method, to measure the optic flow at a location 117 in the visual field 105 generating the first frame 115, first a block of texture 119 is selected that contains the location 117. Next a search is conducted in the second frame 121 over a search space 123 for the block 125 that best matches the first image's block 119. A correlation function is typically used to measure how well two blocks match, hence the name of the algorithm. The displacement between the first frame's block 119 and the second frame's best matching block 125 is used to form the resulting optic flow vector 127, shown in FIG. 2c. This process is repeated over the entire image 115 to compute a complete optic flow field. To summarize, essentially this algorithm tracks texture and picture details such as points and edges, and uses the resulting displacements to measure optic flow. In more advanced versions of this algorithm, ideas from signal processing and estimation theory can be used to improve performance. For example, Kalman filters can be used to aid the tracking of features over multiple sequential images. A discussion of these techniques is beyond the scope of this invention but can be found in the general open literature.
This method of computing optical flow is intuitive. However, it is brute force, and hence computationally intensive when performed on two-dimensional images. However the computational complexity is greatly reduced when performed on one-dimensional images. This is for two reasons: first, because block matching computations need to be performed with blocks of one-dimension rather than two; and second, the variety of displacements to be searched covers one-dimension rather than two. The photoreceptor array of this subsequently discussed invention and of the above-discussed co-pending related patent application "A Photoreceptor Array for Linear Optic Flow Measurement" provide a useful one-dimensional image. Details on this invention will be discussed later.
The feature tracking method of measuring optic flow, also called the token method, is closely related to the correlation method. This method is less popular however is a precursor to the present invention. This correlation method will be briefly discussed by now referring to FIG. 3. FIG. 3 shows a basic outline of a one-dimensional version. An array of feature triggers 129 is located so that the corresponding locations 131 of each feature trigger 133 form an array in the visual field 105. Each feature trigger 133 presents an output 135 to a feature tracking algorithm 137. The feature tracking algorithm 137 generates an output measurement of the optic flow 139. The array of feature triggers 129 are identical and all tuned to respond to some generic image feature. Each feature trigger 133 normally has an output of zero. However when the desired feature moves across a feature trigger location 131, the feature trigger 133 will output a pulse. The feature tracking algorithm 137 then looks for a sequence of pulses moving left or right, and generates an output optic flow measurement dependent on the speed which these pulses are moving in space. The basic difference between the correlation method and the feature tracking method is that in the former the algorithm measures where a block of texture 119 has moved in a given time interval, while in the latter the algorithm measures how long it took a feature to move from one location 131 to the next.
FIGS. 4a and 4b show examples of simple two-dimensional feature detection functions that can be used in the feature triggers. A feature trigger 133 can be implemented by taking the inner product between the feature detection function and the image in the feature trigger's location, then passing the result through a thresholding function. FIG. 4a shows a first derivative detector 141, a feature detector that will be used in the subsequently described present invention. A feature trigger 133 using this feature detection function will respond to vertical edges with the bright side on the +X direction 143. FIG. 4b shows a second derivative detector 145. FIG. 4b is in the shape of the most popular feature detector-a on-dimensional Laplacian funtion. The inner product between this feature and the region of the visual field will cross zero as an edge crosses this feature detector. A feature trigger using this feature detection function will respond best to a bright vertical bar. Another example of a feature detection function is one that responds to an increase in image intensity in the feature trigger's location.
This method is still computationally complex because of the computation needed to compute such features in a two-dimensional image. As described above, such computations are essentially inner products between two matrices. However, the computational complexity is greatly reduced when optic flow is computed with one-dimensional images. The reasons are synonymous with those for the correlation method.
Some researchers have taken the alternative approach of building application specific integrated circuits (ASICs) that use a combination of digital and analog circuitry to measure optical flow. The idea behind this approach is that specifically designed analog and digital circuits can perform the computations necessary to measure optical flow in a much more compact fashion than is possible with a general purpose Von-Neumann type computer. This is especially useful if the implemented algorithm is one that can be mapped onto an array of parallel processors. These efforts have resulted in single or multiple chip systems that do measure optical flow. However the vast majority of these chips still use a two-dimensional pixel-structured representation of the image, which is not necessarily a good representation for optical flow computation. Furthermore in many of these cases the circuits implement hard-wired versions of conventional algorithms. Thus, the speed increase comes only from implementing an algorithm in firmware rather than software, whether or not the algorithm maps elegantly into the hardware. Finally, a significant problem with most of these chips is that they do not function well with low contrast images.
A variant of the use of specialized integrated circuits to measure optical flow is the "neuromorphic engineering" approach. In this approach the architecture and dynamics of circuits mimic what is believed to be happening in the visual processing part of the brain. The neuromorphic engineering community also is developing algorithms that match the dynamics of these neural structures. By far the two most popular features include a sharp increase in image intensity and a zero-crossing of the Laplacian of the visual field intensity in the feature detector's area. Furthermore effort is made to make variations of these algorithms that map elegantly onto VLSI hardware. Thus, creative methods are used to perform various measurements. For example, a discharging capacitor can be used to measure time. This combination of a more elegant means of computation and implementation in hardware results in the implementation of optical flow algorithms in compact circuits. However much work needs to be done with this approach. First, most of these circuits require unrealistically high contrast images in order to function properly. For example, test stimuli often consist of black bars on a white background. Second, most of these algorithms have only been implemented in one dimension and are intended to be used with optic flow parallel to the array's direction. Those chips that do compute two-dimensional optic flow have a very small number of pixels. As a source of ideas, though, this neuromorphic approach is excellent.
The present invention will subsequently addresses the high computational complexity required for optic flow algorithms that operate in two dimensions by borrowing ideas from both image processing and neuromorphic engineering. The sensor is able to detect motion from almost all real world textures. The sensor operates very well with textures having very low contrast. In the first embodiment, optical flow has been successfully measured with texture contrasts down to several percent. Yet the sensor provides information useful for two-dimensional optic flow measurement: a single sensor produces a measurement of the projection of the optic flow vector onto the sensor orientation vector. Hence, several of these sensors can be oriented in different directions to capture the full two-dimensional optic flow information. The sensor maps elegantly into an all VLSI implementation. It also implements easily in a hybrid implementation, where back-end processing is performed on a conventional digital computer. In the hybrid implementation case the computational complexity is orders of magnitude less that that of conventional optic flow algorithms. Thus, this sensor can be implemented a wide variety of ways, depending on the requirements and physical nature of the system using this sensor.